package com.jwetherell.my.search;

public class SearchAlgos {

	/**
	 * Returns index of the key to be found, or -1 if the key is not found
	 */
	public static int interpolationSearch(int [] data, int key) {
		return commonCodeForInterpolationAndBinarySearch(data, key, true);
	}
	
	public static int binarySearch(int [] data, int key) {
		return commonCodeForInterpolationAndBinarySearch(data, key, false);
	}
	
	private static int commonCodeForInterpolationAndBinarySearch(int [] data, int key, boolean isInterpolation) {
		int foundIndex = -1;
		
		int low = 0;
		int high = data.length - 1;
		int mid = low;
		
		while (key >= data[low] && key <= data[high]) {
			if (isInterpolation)
				mid = low +
				         ((key - data[low]) * (high - low)) /
				         (data[high] - data[low]); //out of range is possible  here
			else
				mid = (low + high) / 2;
			
			// Repetition of the comparison code is forced by syntax limitations.
			if (key == data[mid])
				return mid;
			else if (key > data[mid])
				low = mid + 1;
			else
				high = mid - 1;
		}
		
		if (data[low] == key)
			   return low;
		
		return foundIndex;
	}
}
